package sort;
//快速排序
public class Quick {
    public static void sort(Comparable[] a ){
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    private static void sort(Comparable[] a ,int lo , int hi){
        if (hi <= lo){
            return;
        }
        int par = partition(a, lo, hi);
        sort(a,lo,par-1);
        sort(a,par+1,hi);
    }
    private static int partition(Comparable[] a ,int lo,int hi){
        Comparable key = a[lo];
        int left = lo;
        int right = hi+1;
        while (true){
            while (grate(a[--right],key)){
                if (right == lo){
                    break;
                }
            }
            while (grate(key,a[++left])){
                if (left == hi){
                    break;
                }
            }
            if (left >= right){
                break;
            }else {
                exch(a,left,right);
            }
        }
        exch(a,lo,right);
        return right;
    }
    //判断两个数值的大小
    private static Boolean grate(Comparable x, Comparable y){
        return x.compareTo(y) > 0;
    }
    //交换两个元素的位置
    private static void exch(Comparable[] a, int i ,int j){
        Comparable tem = a[i];
        a[i] = a[j];
        a[j] = tem;
    }
}
